package stack;

/**
 * 栈的顺序存储结构 LIFO
 * 
 * @author mengxin
 * 
 * @param <T>
 */
public class ArrayStack<T> implements Stack<T> {

	private T[] t = (T[]) new Object[16];// 栈空间默认为16

	private int size = 0;

	@Override
	public boolean isEmpty() {
		return size == 0;
	}

	@Override
	public void clear() {
		for (int i = 0; i < t.length; i++)
			t[i] = null;// 将其引用只为null，方便gc进行回收
		size = 0;// 栈的大小置0
	}

	/* 弹栈操作 */
	@Override
	public T pop() {
		if (size == 0)
			return null;
		else {
			T tmp = t[size - 1];
			t[size - 1] = null;// 便于gc回收
			size--;
			return tmp;
		}
	}

	/**
	 * 入栈操作
	 */
	@Override
	public boolean push(T data) {
		if (size >= t.length) {
			// 栈空间已满，需要扩容
			resize();
		}
		t[size++] = data;
		return true;
	}

	private void resize() {
		T[] tmp = (T[]) new Object[t.length * 2];
		for (int i = 0; i < t.length; i++) {
			tmp[i] = t[i];
			t[i] = null;// 便于gc处理
		}
		t = tmp;
		tmp = null;// 便于gc处理，提高程序效率
	}

	@Override
	public int length() {
		return size;
	}

	/* 查看栈顶元素，但是并不删除 */
	@Override
	public T peek() {
		if (size == 0)
			return null;
		else {
			return t[size - 1];
		}
	}

	/* 下表从1开始 */
	@Override
	public int search(T t) {
		for (int i = 0; i < size; i++)
			if (t.equals(this.t[i]))
				return i + 1;
		return 0;
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("ArrayStack:\n[\n");
		for (int i = size - 1; i >= 0; i--) {
			sb.append("   " + t[i].toString());
			if (i != size + 1) {
				sb.append("\n");
			}
		}
		sb.append("]");
		return sb.toString();
	}

	public static void main(String[] args) throws Exception{
		Stack<Integer> stack = new ArrayStack<Integer>();
		stack.push(1);
		stack.push(2);
		System.out.println("Stack length:"+stack.length());
		System.out.println(stack.toString());
		System.out.println(stack.search(2));
		System.out.println(stack.pop());
		System.out.println(stack.toString());
		stack.clear();
		System.out.println(stack.toString());
		
	}
}
